# -*- coding: utf-8 -*-
"""
Created on Wed Apr 22 19:23:13 2020
如果获取的图片不完整请先用lnkscape或Ai描边处理图片或其他P图软件处理一遍
如果获取的图片不完整请先用lnkscape或Ai描边处理图片或其他P图软件处理一遍
如果获取的图片不完整请先用lnkscape或Ai描边处理图片或其他P图软件处理一遍
重要的事说三遍
@author: PuddingMShake
"""

from PIL import Image
import pylab
fig, ax = pylab.subplots()
picname=input('Image name:')
img=Image.open(picname)
img=img.convert('L')
threshold=int(input('threshold:'))
contours=ax.contour(img,origin='image',levels=[threshold])
import numpy as np
raw_data = []
segs = np.array(contours.allsegs) / max(img.width, img.height)
reverse_idx = {}
for seg in segs:
    for poly in seg:
        # down sample 1: make points more discrete
        poly = (np.array(poly) * 1000).astype(int) / 1000
        poly = [tuple(p) for p in poly]

        # index points and deduplicate points shared cross polygons
        poly2 = []
        for p in poly:
            if p not in reverse_idx:
                reverse_idx[p] = len(reverse_idx)
                raw_data.append(np.array(p))
print(f'{len(raw_data)} points in raw data')

indices = np.random.choice(len(raw_data), int(len(raw_data) * 0.3), replace=False)
samples = np.array(raw_data)[indices]
print(f'randomly sampled {len(samples)} points')
from scipy.spatial import Delaunay
import heapq

def dis(samples, i, j):
        return np.linalg.norm(samples[i] - samples[j])

def mst(samples):
        n = len(samples)
        tri = Delaunay(samples)
        g = [[] for i in range(n)]
        edges = {}
        nodes = set()
        for simplex in tri.simplices:
            nodes |= set(simplex)
            for k in range(3):
                i, j = simplex[k - 1], simplex[k]
                edge = min(i, j), max(i, j)
                if edge not in edges:
                    edges[edge] = dis(samples, i, j)
        pq = [(d, i, j) for ((i, j), d) in edges.items()]
        heapq.heapify(pq)
        p = list(range(n))

        def union(i, j):
            p[find(i)] = find(j)

        def find(i):
            if p[i] == i:
                return i
            p[i] = find(p[i])
            return p[i]

        # Kruskal
        cc = len(nodes)
        while cc > 1:
            d, i, j = heapq.heappop(pq)
            if find(i) != find(j):
                union(i, j)
                g[i].append((j, d))
                g[j].append((i, d))
                cc -= 1
        return g

g = mst(samples)
print(f'Generated minimum spanning tree with {len(g)} nodes.')
def find_farthest_leaf_pair(g):
    def dfs(i, parent):
        """
        Return
            - farthest leaf id in thissubtree and distance to root i
            - farthest leave pair in this subtree and distance between them
        """
        farthest_leaf = i
        farthest_leaf_dis = 0
        farthest_leaf_pair = None
        farthest_leaf_pair_dis = -1
        leave_dis = []
        for j, _ in g[i]:
            if j == parent:
                continue
            l, ld, pair, pair_dis = dfs(j, i)
            leave_dis.append((ld + 1, l))
            if ld + 1 > farthest_leaf_dis:
                farthest_leaf_dis = ld + 1
                farthest_leaf = l
            if farthest_leaf_pair_dis < pair_dis:
                farthest_leaf_pair = pair
                farthest_leaf_pair_dis = pair_dis
        if len(leave_dis) >= 2:
            (d1, l1), (d2, l2) = sorted(leave_dis)[-2:]
            if d1 + d2 > farthest_leaf_pair_dis:
                farthest_leaf_pair_dis = d1 + d2
                farthest_leaf_pair = l1, l2
        return farthest_leaf, farthest_leaf_dis, farthest_leaf_pair, farthest_leaf_pair_dis

    for i in range(len(g)):
        if len(g[i]):
            l, ld, pair, pair_dis = dfs(i, -1)
            if len(g[i]) == 1 and ld > pair_dis:
                return i, l
            return pair

st, ed = find_farthest_leaf_pair(g)
print(f'Find the farthest leaves pair {samples[st]} {samples[ed]}')
def rearange_children_order(g, st, ed):
    vis = set()

    def dfs(i):
        vis.add(i)
        if i == ed:
            return True
        for j in range(len(g[i])):
            if g[i][j][0] not in vis:
                if dfs(g[i][j][0]):
                    g[i][j], g[i][-1] = g[i][-1], g[i][j]
                    return True
        return False
    dfs(st)
    return st, ed
rearange_children_order(g, st, ed)
print('MST children reordered')
def generate_path(g, st, ed):
    res = []
    vis = set()

    def dfs(i):
        vis.add(i)
        res.append(samples[i])
        if i == ed:
            return True
        leaf = True
        for j, _ in g[i]:
            if j not in vis:
                leaf = False
                if dfs(j):
                    return True
        if not leaf:
            res.append(samples[i])
        return False
    dfs(st)
    return res

path = generate_path(g, st, ed)
print(f'generated path of {len(path)} points')
from scipy.fftpack import fft
path = np.array(path)
X = fft(path[..., 0] + path[..., 1] * 1j)
file=open('fft_data.json','w')
file.write('[')
for c in X[0:-1]:
    file.write('{')
    file.write('\"x\":'+str(c.real)+',\"y\":'+str(c.imag))
    file.write('},')
file.write('{')
file.write('\"x\":'+str(X[len(X)-1].real)+',\"y\":'+str(X[len(X)-1].imag))
file.write('}')
file.write(']')
file.close()


